/**
* 求解约瑟夫环的问题
**/
#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
  int data;
  struct _node * next; // 指向下一个
} node;

typedef struct {
  node * head; // 队列头指针
  node * tail; // 队列最后一个元素的指针
} queue;

/**
* 创建个数为n的循环链表
**/
queue *create_queue()
{
  queue * p = (queue *)malloc(sizeof(queue));
  if (NULL == p) {
    exit(-1);
  }
  p->head = NULL;
  p->tail = NULL;
  return p;
}

// 入队
int enqueue(queue *p, int n)
{
  node *q = (node*)malloc(sizeof(node));
  if (NULL == q) {
    exit(-1);
  }
  q->data = n;
  q->next = NULL;
  
  if (NULL == p->head) { // 1.首次入队,2.元素全部出队后
    p->head = p->tail = q; // 入队第一个元素
  } else {
    p->tail->next = q;
    p->tail = q;
  }
  
  return 0;
}

// 出队
int dequeue(queue *p)
{
  node *q  = p->head; // 缓存队首
  if (NULL == q) {
    return -1; // 队列已经没有元素了
  }
  int data = q->data; // 得到队首元素
  p->head  = q->next; // 将队首后移,当出最后一个元素时,p->head=NULL
  free(q); // 释放内存
  return data; // 返回队首值
}

// 打印整个循环链表
void print_queue(queue *q)
{
  node *p = q->head;
  while (NULL != p) {
    printf("%d,", p->data);
    p = p->next;
  }
  printf("\n");
}

// 入栈
int push_stack(node **stack, int n)
{
  node *p = (node*)malloc(sizeof(node));
  if (NULL == p) {
    exit(-1);
  }
  
  p->data = n;
  p->next = *stack;
  *stack  = p;
}

// 弹栈
int pop_stack(node **stack)
{
  if (*stack == NULL) {
    return -1; // 栈空了,没法弹栈
  }
  node * p = *stack;
  *stack = p->next;
  int data = p->data;
  free(p);
  return data;
}

// 打印栈
void print_stack(node *stack)
{
  node *p = stack;
  while (NULL != p) {
    printf("%d,", p->data);
    p = p->next;
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  queue *start = create_queue();
  
  int i;
  for (i=0;i<10;i++) {
    enqueue(start, i);
  }
  print_queue(start);
  
  while (start->head != NULL) {
    printf("%d->", dequeue(start));
  }
  printf("\n");
  
  for (i=0;i<10;i++) {
    enqueue(start, 10-i);
  }
  print_queue(start);
  
  while (start->head != NULL) {
    printf("%d->", dequeue(start));
  }
  printf("\n");
  
  // 下面是栈操作
  node *stack = NULL; // 创建一个空栈
  for (i=0;i<10;i++) {
    push_stack(&stack, i);
  }
  print_stack(stack);
  
  while (stack != NULL) {
    printf("%d->", pop_stack(&stack));
  }
  printf("\n");
  
  return 0;
}
